//
//
// 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿
//过地下城并通过对抗恶魔来拯救公主。 
//
// 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 
//
// 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么
//包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 
//
// 为了尽快到达公主，骑士决定每次只向右或向下移动一步。 
//
// 
//
// 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 
//
// 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。 
//
// 
// 
// -2 (K) 
// -3 
// 3 
// 
// 
// -5 
// -10 
// 1 
// 
// 
// 10 
// 30 
// -5 (P) 
// 
// 
//
//
// 
//
// 说明: 
//
// 
// 
// 骑士的健康点数没有上限。 
// 
// 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。 
// Related Topics数组 | 动态规划 | 矩阵 
//
// 👍 650, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class DungeonGame {
    public static void main(String[] args) {
        Solution solution = new DungeonGame().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 自顶向下，参照labuladong：https://labuladong.gitee.io/algo/3/28/87/
        /*int[][] memo;

        public int calculateMinimumHP(int[][] dungeon) {
            int m = dungeon.length, n = dungeon[0].length;
            memo = new int[m][n];
            for (int i = 0; i < m; i++) {
                Arrays.fill(memo[i], -1);
            }

            return dp(dungeon, 0, 0);
        }

        // 表示从dungeon[i][j]到达终点所需要的生命值
        private int dp(int[][] dungeon, int i, int j) {
            int m = dungeon.length, n = dungeon[0].length;

            if (i == m - 1 && j == n - 1) {
                // 一开始就在终点
                return dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
            }

            // 越界处理
            if (i == m || j == n) {
                // 返回最大的，后面就计算不到
                return Integer.MAX_VALUE;
            }

            if (memo[i][j] != -1) {
                return memo[i][j];
            }

            // 状态转移逻辑
            int res = Math.min(dp(dungeon, i + 1, j), dp(dungeon, i, j + 1)) - dungeon[i][j];

            // 骑士的生命值至少为 1
            memo[i][j] = res <= 0 ? 1 : res;
            return memo[i][j];
        }*/

        // 自底向上：https://labuladong.gitee.io/algo/3/28/87/
        public int calculateMinimumHP(int[][] dungeon) {
            int m = dungeon.length, n = dungeon[0].length;
            // 表示从dungeon[i][j]到终点需要的最小生命值
            int[][] dp = new int[m][n];
            // 一开始就是终点
            dp[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;

            for (int i = m - 2; i >= 0; i--) {
                int res = dp[i + 1][n - 1] - dungeon[i][n - 1];
                dp[i][n - 1] = res <= 0 ? 1 : res;
            }

            for (int i = n - 2; i >= 0; i--) {
                int res = dp[m - 1][i + 1] - dungeon[m - 1][i];
                dp[m - 1][i] = res <= 0 ? 1 : res;
            }

            for (int i = m - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                    int res = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                    dp[i][j] = res <= 0 ? 1 : res;
                }
            }

            return dp[0][0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
